package com.lwl.Algorithmic_data_structure.class12二叉树;

import com.lwl.Utils.MyTreeNode;

/**
 * @author lwl
 * @Description 是否完全二叉树
 * @date 2023/6/1 9:05
 */
public class Code06isCompleteBT {

    class Info {

        /**
         * 是否满二叉树
         */
        boolean isFull;

        /**
         * 是否完全二叉树
         */
        boolean isComplete;

        int level;

        public Info(boolean isFull, boolean isComplete, int level) {
            this.isFull = isFull;
            this.isComplete = isComplete;
            this.level = level;
        }
    }

    /**
     * treeNode为头的树要是完全二叉树需要满足以下任一条件
     * 1. 左满 右满 --> 左高 == 右高
     * 2. 左满 右满 --> 左高 == 右高 + 1
     * 3. 左完全 右满 --> 左高 == 右高 + 1
     * 4. 左满 右完全 --> 左高 == 右高
     * <p>
     * 除此之外，都不满足treeNode是完全二叉树的条件
     */
    public Info isCompleteBT(MyTreeNode treeNode) {
        if (treeNode == null) {
            return new Info(true, true, 0);
        }
        Info leftInfo = isCompleteBT(treeNode.left);
        Info rightInfo = isCompleteBT(treeNode.right);

        boolean isFull = (leftInfo.isFull && rightInfo.isFull) && (leftInfo.level == rightInfo.level);
        boolean isComplete = false;
        int level = Math.max(leftInfo.level, rightInfo.level) + 1;
        if (leftInfo.isFull && rightInfo.isFull && leftInfo.level == rightInfo.level) {
            isComplete = true;
        } else if (leftInfo.isFull && rightInfo.isFull && leftInfo.level == rightInfo.level + 1) {
            isComplete = true;
        } else if (leftInfo.isComplete && rightInfo.isFull && leftInfo.level == rightInfo.level + 1) {
            isComplete = true;
        } else if (leftInfo.isFull && rightInfo.isComplete && leftInfo.level == rightInfo.level) {
            isComplete = true;
        }

        return new Info(isFull, isComplete, level);
    }

}
